package MovingWindowSeries;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class MinWindowSolution_76 {
    // 存放字符串s和t中每个字符的数量
    Map<Character, Integer> oriMap = new HashMap<Character, Integer>();
    Map<Character, Integer> curMap = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            oriMap.put(c, oriMap.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = -1;
        // len: 当前窗口大小，ansL: 窗口左边界，ansR: 窗口右边界
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        // 扩大窗口的右边界 right，并检查当前字符是否在 t 中。如果是，将其频率加一
        while (right < sLen) {
            ++right;
            if (right < sLen && oriMap.containsKey(s.charAt(right))) {
                curMap.put(s.charAt(right), curMap.getOrDefault(s.charAt(right), 0) + 1);
            }
            // 缩小窗口的左边界 left，并检查当前字符是否不在 t 中。如果是，将其频率减一
            while (check() && left <= right) {
                if (right - left + 1 < len) {
                    len = right - left + 1; // 更新窗口大小
                    ansL = left; // 更新窗口左边界
                    ansR = left + len; // 更新窗口右边界
                }
                if (oriMap.containsKey(s.charAt(left))) {
                    curMap.put(s.charAt(left), curMap.getOrDefault(s.charAt(left), 0) - 1);
                }
                ++left;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    /**
     * 判断当前窗口是否包含所有 t 中的字符。若 curMap 中某个字符的数量小于 oriMap 中的数量，则返回 false
     * @return
     */
    public boolean check() {
        Iterator iter = oriMap.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            // 若 curMap 中某个字符的数量小于 oriMap 中的数量
            // 返回 false，不满足条件
            if (curMap.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }
}
